1207. Корень, логарифм, синус

Злой профессор только что задал Вам следующую задачу. Определим последовательность следующим образом:

x₀ = 1,

x_i = + +

Для каждого значения i вычислите x_i.

Вход. Состоит из нескольких строк, каждая из которых содержит одно целое число – значение i, которое не меньше 0 и не больше 10⁶. Последняя строка содержит -1 и не обрабатывается.

Выход. Для каждого значения i (кроме последнего -1) выведите соответствующее значение x_i, вычисленное по модулю 10⁶.

Пример входа	Пример выхода
0 1 2 10 -1	1 3 5 21

РЕШЕНИЕ

рекуррентное соотношение

Анализ алгоритма

Значение x_i будем вычислять при помощи функции f(i). Для этого следует реализовать рекуррентность

= + + ,

с запоминанием f(i) в линейном массиве dp размером 10⁶.

Реализация алгоритма

Значения x_i будем хранить в массиве dp.

#define MAX 1000001

int dp[MAX];

Функция f(n) вычисляет значение x_n.

int f(int n)

{

Условие окончания рекурсии.

if (n == 0) return 1;

Если x_n уже вычислено (dp[n] ≠ -1), то возвращаем его.

if (dp[n] != -1) return dp[n];

Вычисляем рекурсивно первое, второе и третье слагаемое.

int a = f((int)(n - sqrt(n)));

int b = f((int)(log(n)));

int c = f((int)(n * sin(n) * sin(n)));

Вычисляем, запоминаем и возвращаем значение x_n.

return dp[n] = (a + b + c) % 1000000;

}

Основная часть программы. Положим dp[i] = -1, если x_i не вычислено. Читаем входное значение n и выводим ответ.

memset(dp,-1,sizeof(dp));

while(scanf("%d",&n), n != -1)

printf("%d\n",f(n));

Реализация алгоритма – не рекурсивная

#include <stdio.h>

#include <math.h>

int i, n;

int x[1000001];

int main(void)

{

x[0] = 1;

for (i = 1; i <= 1000000; i++)

x[i] = (x[(int)(i - sqrt(i))] + x[(int)(log(i))] +

x[(int)(i * sin(i) * sin(i))]) % 1000000;

while (scanf("%d", &n), n != -1)

printf("%d\n", x[n]);

return 0;

}

Java реализация

import java.util.*;

public class Main

{

static int dp[] = new int[1000001];

static int f(int n)

{

if (n == 0) return 1;

if (dp[n] != -1) return dp[n];

int a = f((int)(n - Math.sqrt(n)));

int b = f((int)(Math.log(n)));

int c = f((int)(n * Math.sin(n) * Math.sin(n)));

return dp[n] = (a + b + c) % 1000000;

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

Arrays.fill(dp, -1);

while(true)

{

int n = con.nextInt();

if (n == -1) break;

System.out.println(f(n));

}

con.close();

}

}